package Algorithm.Search;

/**
 * 在介绍插值查找之前，先考虑一个问题：
 * 为什么二分查找算法一定要是折半，而不是折四分之一或者折更多呢？
 * 其实就是因为方便，简单，但是如果我能在二分查找的基础上，让中间的mid点，尽可能靠近想要查找的元素，那不就能提高查找的效率了吗？
 * 二分查找中查找点计算如下：
 * 　　mid=(low+high)/2, 即mid=low+1/2*(high-low);
 * 我们可以将查找的点改进为如下：
 * 　　mid=low+(high-low)(key-a[low])/(a[high]-a[low])，
 * 这样，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。
 * 　　基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。
 * *细节：**对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。
 * 代码跟二分查找类似，只要修改一下mid的计算方式即可。
 */
public class InterpolationSearch {
    public static void main(String[] args) {
        // 插值查找也属于有序查找
        // 插值查找也是对于二分查找的一个扩展（mid值的计算不一样）
        // 插值查找是对于数据分布比较均匀时使用
        //  arr|_______|____|______________________|
        //     ↑       ↑    ↑                      ↑
        //    low  target  mid                    high
        // mid的计算方式为： mid = low + (high - low) * (target) - arr[low]) / (arr[high] - arr[low])
        // (target) - arr[low]) / (arr[high] - arr[low])为计算target在集合中分布情况(在集合中找一个接近target的值)
        // 再乘上一个（high + low）为计算target在数组中分布情况的索引位置
        int[] arr = {4, 10, 12, 15, 18, 25, 28, 35, 36, 48, 51, 56, 78, 90, 110, 254};

        int target = 3;
        int start = 0;
        int end = arr.length - 1;
        while (start <= end) {
            // 分母(target - arr[start]) / (arr[end] - arr[start])表示target在数组的所占比例
            // 方式1：mid = (end + start) * ((target - arr[start]) / (arr[end] - arr[start]))
            // 方式2：mid = start + (end - start) * ((target - arr[start]) / (arr[end] - arr[start]))
            // 方式1的end + start当数据过大时可能会导致溢出
            int mid = start + (end - start) * ((target - arr[start]) / (arr[end] - arr[start]));
            if (arr[mid] > target) {
                end = mid - 1;
            } else if (arr[mid] < target) {
                start = mid + 1;
            } else {
                System.out.println("存在");
                return;
            }
        }
        System.out.println("不存在");
    }
}
